package com.wc.alorithm.string.trietree;

/**
 * @Author congege
 * @Description 01Tire
 * @Date Created in 2023/12/3-11:42
 */
public class _01Trie {
    private static int N = (int) 1e5 + 10, M = N * 31;
    private int[][] son = new int[M][2];
    private int idx = 0;
    private boolean[] exist = new boolean[M];

    public void insert(int x) {
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            // 判断最高位置的是1还是0
            int u = x >> i & 1;
            if (son[p][u] == 0) {
                son[p][u] = ++idx;
            }
            p = son[p][u];
        }
        exist[p] = true;
    }

    public boolean query(int x) {
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int u = x >> i & 1;
            if (son[p][u] == 0) {
                return false;
            }
            p = son[p][u];
        }
        return exist[p];
    }
}
